package TOP101;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;

/**
 * @Question BM12
 * @Date 2022/11/4 11:06
 * @Solution
 */
public class BM12 {
    //归并法 时间复杂度：O(NlogN) 空间复杂度O(1)
    public ListNode sortInList(ListNode head) {
        if(head==null || head.next==null) {
            return head;
        }
        //寻找重点
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast!=null && fast.next!=null) {
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode temp=slow.next;
        slow.next=null;
        //递归左右排序
        ListNode left =sortInList(head);
        ListNode right =sortInList(temp);
        //合并
        ListNode ans=new ListNode(0);
        ListNode cur = ans;
        while(left!=null&&right!=null) {
            ListNode node =null;
            if(left.val < right.val) {
                node = new ListNode(left.val);
                left=left.next;
            } else {
                node = new ListNode(right.val);
                right=right.next;
            }
            cur.next=node;
            cur=node;
        }
        while(left!=null) {
            ListNode node = new ListNode(left.val);
            cur.next=node;
            cur=node;
            left=left.next;
        }
        while(right!=null) {
            ListNode node = new ListNode(right.val);
            cur.next=node;
            cur=node;
            right=right.next;
        }
        return ans.next;
    }
    //辅助数组法 时间复杂度：O(NlogN) 空间复杂度O(N)
//    public ListNode sortInList (ListNode head) {
//        ArrayList<Integer> arrayList = new ArrayList<>();
//        while(head!=null) {
//            arrayList.add(head.val);
//            head=head.next;
//        }
//        arrayList.sort(new Comparator<Integer>() {
//            @Override
//            public int compare(Integer o1, Integer o2) {
//                return o1-o2;
//            }
//        });
//        ListNode ans = new ListNode(0);
//        ListNode cur = ans;
//        while(!arrayList.isEmpty()) {
//            ListNode node = new ListNode(arrayList.remove(0));
//            cur.next=node;
//            cur=node;
//        }
//        return ans.next;
//    }
}
